package com.zup.algorithm.sort;

import com.zup.algorithm.util.SortUtils;

import java.util.Arrays;

/**
 * 说明：冒泡排序
 *
 * @author Created by xujinyan on 2018/5/14.
 */
public class BubbleSort {
    public static void sort(int[] arr) {
        // 需要排序的元素下标
        for (int i=0; i<arr.length; i++) {
            // 对每个元素冒泡至arr.length-i
            for (int j=0; j<arr.length-1-i; j++) {
                if (arr[j] > arr[j+1]) {
                    SortUtils.swap(arr, j, j+1);
                }
            }
        }
    }

    /**
     * 如果一趟冒泡没有经过交换，则表示数组已经有序，提前结束
     */
    public static void sortImprove(int[] arr) {
        // 需要排序的元素下标
        for (int i=0; i<arr.length; i++) {
            int flag = 0;
            // 对每个元素冒泡至arr.length-i
            for (int j=0; j<arr.length-1-i; j++) {
                if (arr[j] > arr[j+1]) {
                    flag = 1;
                    SortUtils.swap(arr, j, j+1);
                }
            }
            if (flag == 0) {
                break;
            }
        }
    }

    /**
     * 记录最后一次冒泡的位置，后面就已经是有序的了
     */
    public static void sortImprove2(int[] arr) {
        // 需要排序的元素下标
        for (int i=0; i<arr.length; i++) {
            int flag = 0;
            // 对每个元素冒泡至arr.length-i
            for (int j=0; j<arr.length-1-i || j<flag; j++) {
                if (arr[j] > arr[j+1]) {
                    flag = j;
                    SortUtils.swap(arr, j, j+1);
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = SortUtils.generateArr(10, 10);
        BubbleSort.sortImprove2(arr);
        System.out.println(Arrays.toString(arr));
    }
}
